SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Needleman–Wunsch algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Needleman–Wunsch algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><tbody><tr><td colspan="2" class="infobox-image"><div class="infobox-caption">Figure 1: Needleman-Wunsch pairwise sequence alignment</div></td></tr><tr><th scope="row" class="infobox-label">Class</th><td class="infobox-data"><a href="Sequence_alignment" title="Sequence alignment">Sequence alignment</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Worst-case</a> <a href="Time_complexity" title="Time complexity">performance</a></th><td class="infobox-data"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn)}</annotation>

</semantics>

</math></span><img src="./89ea09572a098b4762141a22c43a7ba1c20051cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.018ex; height:2.843ex;" alt="{\displaystyle O(mn)}" loading="lazy"></span></td></tr><tr><th scope="row" class="infobox-label"><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Worst-case</a> <a href="Space_complexity" title="Space complexity">space complexity</a></th><td class="infobox-data"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn)}</annotation>

</semantics>

<p>The <b>Needleman–Wunsch algorithm</b> is an <a href="Algorithm" title="Algorithm">algorithm</a> used in <a href="Bioinformatics" title="Bioinformatics">bioinformatics</a> to <a href="Sequence_alignment" title="Sequence alignment">align</a> <a href="Protein" title="Protein">protein</a> or <a href="Nucleotide" title="Nucleotide">nucleotide</a> sequences. It was one of the first applications of <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> to compare biological sequences. The algorithm was developed by Saul B. Needleman and Christian D. Wunsch and published in 1970.<sup id="cite_ref-Needleman_1-0" class="reference"><a href="#cite_note-Needleman-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The algorithm essentially divides a large problem (e.g. the full sequence) into a series of smaller problems, and it uses the solutions to the smaller problems to find an optimal solution to the larger problem.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> It is also sometimes referred to as the <a href="Optimal_matching" title="Optimal matching">optimal matching</a> algorithm and the <a href="Sequence_alignment#Global_and_local_alignments" title="Sequence alignment">global alignment</a> technique. The Needleman–Wunsch algorithm is still widely used for optimal global alignment, particularly when the quality of the global alignment is of the utmost importance. The algorithm assigns a score to every possible alignment, and the purpose of the algorithm is to find all possible alignments having the highest score.

</p>

<div class="mw-heading mw-heading2"><h2 id="Introduction">Introduction</h2></div>

<p>This algorithm can be used for any two <a href="String_(computer_science)" title="String (computer science)">strings</a>. This guide will use two small <a href="DNA_sequences" class="mw-redirect" title="DNA sequences">DNA sequences</a> as examples as shown in Figure 1:

</p>

<pre>GCATGCG

GATTACA

</pre>

<div class="mw-heading mw-heading3"><h3 id="Constructing_the_grid">Constructing the grid</h3></div>

<p>First construct a grid such as one shown in Figure 1 above. Start the first string in the top of the third column and start the other string at the start of the third row. Fill out the rest of the column and row headers as in Figure 1. There should be no numbers in the grid yet.

</p>

<th>G

</th></tr>

<tr>

</th>

<td>

</td></tr>

<tr>

<th scope="row">G

</th>

<td>

</td></tr>

<tr>

<th scope="row">A

</th>

<td>

</td></tr>

<tr>

<th scope="row">T

</th>

<td>

</td></tr>

<tr>

<th scope="row">T

</th>

<td>

</td></tr>

<tr>

<th scope="row">A

</th>

<td>

</td></tr>

<tr>

<th scope="row">C

</th>

<td>

</td></tr>

<tr>

<th scope="row">A

</th>

<td>

</td></tr></tbody></table>

<div class="mw-heading mw-heading3"><h3 id="Choosing_a_scoring_system">Choosing a scoring system</h3></div>

<p>Next, decide how to score each individual pair of letters. Using the example above, one possible alignment candidate might be:

</p>

<pre>12345678

<samp class="dna-sequence" style="word-break: break-all;">GCATG-CG</samp>

<samp class="dna-sequence" style="word-break: break-all;">G-ATTACA</samp>

</pre>

<p>The letters may match, mismatch, or be matched to a gap (a deletion or insertion (<a href="Indel" title="Indel">indel</a>)):

</p>

<ul><li>Match: The two letters at the current index are the same.</li>

<li>Mismatch: The two letters at the current index are different.</li>

<li>Indel (Insertion or Deletion): The best alignment involves one letter aligning to a gap in the other string.</li></ul>

<p>Each of these scenarios is assigned a score and the sum of the scores of all the pairings is the score of the whole alignment candidate. Different systems exist for assigning scores; some have been outlined in the <a href="#Scoring_systems">Scoring systems</a> section below. For now, the system used by Needleman and Wunsch<sup id="cite_ref-Needleman_1-1" class="reference"><a href="#cite_note-Needleman-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> will be used:

</p>

<ul><li>Match: +1</li>

<li>Mismatch or Indel: −1</li></ul>

<p>For the Example above, the score of the alignment would be 0:

</p>

<pre><samp class="dna-sequence" style="word-break: break-all;">GCATG-CG</samp>

<samp class="dna-sequence" style="word-break: break-all;">G-ATTACA</samp>

+−++−−+− −> 1*4 + (−1)*4 = 0

</pre>

<div class="mw-heading mw-heading3"><h3 id="Filling_in_the_table">Filling in the table</h3></div>

<p>Start with a zero in the first row, first column (not including the cells containing nucleotides). Move through the cells row by row, calculating the score for each cell. The score is calculated by comparing the scores of the cells neighboring to the left, top or top-left (diagonal) of the cell and adding the appropriate score for match, mismatch or indel. Take the maximum of the candidate scores for each of the three possibilities:

</p>

<ul><li>The path from the top or left cell represents an indel pairing, so take the scores of the left and the top cell, and add the score for indel to each of them.</li>

<li>The diagonal path represents a match/mismatch, so take the score of the top-left diagonal cell and add the score for match if the corresponding bases (letters) in the row and column are matching or the score for mismatch if they do not.</li></ul>

<p>The resulting score for the cell is the highest of the three candidate scores.

</p><p>Given there is no 'top' or 'top-left' cells for the first row only the existing cell to the left can be used to calculate the score of each cell. Hence −1 is added for each shift to the right as this represents an indel from the previous score. This results in the first row being 0, −1, −2, −3, −4, −5, −6, −7. The same applies to the first column as only the existing score above each cell can be used. Thus the resulting table is:

</p>

<th>G

</th></tr>

<tr>

</th>

<td>−7

</td></tr>

<tr>

<th scope="row">G

</th>

<td>

</td></tr>

<tr>

<th scope="row">A

</th>

<td>

</td></tr>

<tr>

<th scope="row">T

</th>

<td>

</td></tr>

<tr>

<th scope="row">T

</th>

<td>

</td></tr>

<tr>

<th scope="row">A

</th>

<td>

</td></tr>

<tr>

<th scope="row">C

</th>

<td>

</td></tr>

<tr>

<th scope="row">A

</th>

<td>

</td></tr></tbody></table>

<p>The first case with existing scores in all 3 directions is the intersection of our first letters (in this case G and G). The surrounding cells are below:

</p>

<th>G

</th></tr>

<tr>

</th>

<td>−1

</td></tr>

<tr>

<th scope="row">G

</th>

</td></tr></tbody></table>

<p>This cell has three possible candidate sums:

</p>

<ul><li>The diagonal top-left neighbor has score 0. The pairing of G and G is a match, so add the score for match: 0+1 = 1</li>

<li>The top neighbor has score −1 and moving from there represents an indel, so add the score for indel: (−1) + (−1) = (−2)</li>

<li>The left neighbor also has score −1, represents an indel and also produces (−2).</li></ul>

<p>The highest candidate is 1 and is entered into the cell:

</p>

<th>G

</th></tr>

<tr>

</th>

<td>−1

</td></tr>

<tr>

<th scope="row">G

</th>

</td></tr></tbody></table>

<p>The cell which gave the highest candidate score must also be recorded. In the completed diagram in figure 1 above, this is represented as an arrow from the cell in row and column 2 to the cell in row and column 1.

</p><p>In the next example, the diagonal step for both X and Y represents a mismatch:

</p>

<th>C

</th></tr>

<tr>

</th>

<td>−2

</td></tr>

<tr>

<th scope="row">G

</th>

</td></tr>

<tr>

<th scope="row">A

</th>

<td>

</td></tr></tbody></table>

<p>X:

</p>

<p>Y:

</p>

<p>For both X and Y, the highest score is zero:

</p>

<th>C

</th></tr>

<tr>

</th>

<td>−2

</td></tr>

<tr>

<th scope="row">G

</th>

</td></tr>

<tr>

<th scope="row">A

</th>

<td>

</td></tr></tbody></table>

<p>The highest candidate score may be reached by two of the neighboring cells:

</p>

<th>G

</th></tr>

<tr>

<th scope="row">T

</th>

<td>1

</td></tr>

<tr>

<th scope="row">A

</th>

</td></tr></tbody></table>

<p>In this case, all directions reaching the highest candidate score must be noted as possible origin cells in the finished diagram in figure 1, e.g. in the cell in row and column 6.

</p><p>Filling in the table in this manner gives the scores of all possible alignment candidates, the score in the cell on the bottom right represents the alignment score for the best alignment.

</p>

<div class="mw-heading mw-heading3"><h3 id="Tracing_arrows_back_to_origin">Tracing arrows back to origin</h3></div>

<p>Mark a path from the cell on the bottom right back to the cell on the top left by following the direction of the arrows. From this path, the sequence is constructed by these rules:

</p>

<ul><li>A diagonal arrow represents a match or mismatch, so the letter of the column and the letter of the row of the origin cell will align.</li>

<li>A horizontal or vertical arrow represents an indel. Vertical arrows will align a gap ("-") to the letter of the row (the "side" sequence), horizontal arrows will align a gap to the letter of the column (the "top" sequence).</li>

<li>If there are multiple arrows to choose from, they represent a branching of the alignments. If two or more branches all belong to paths from the bottom right to the top left cell, they are equally viable alignments. In this case, note the paths as separate alignment candidates.</li></ul>

<p>Following these rules, the steps for one possible alignment candidate in figure 1 are:

</p>

A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA → <b>G-ATTACA</b>

↓

(branch) → TGCG → -TGCG → ...

→ TACA → TTACA → ...

</pre>

<div class="mw-heading mw-heading2"><h2 id="Scoring_systems">Scoring systems</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Basic_scoring_schemes">Basic scoring schemes</h3></div>

<p>The simplest scoring schemes simply give a value for each match, mismatch and indel. The step-by-step guide above uses match = 1, mismatch = −1, indel = −1. Thus the lower the alignment score the larger the <a href="Levenshtein_distance" title="Levenshtein distance">edit distance</a>, for this scoring system one wants a high score. Another scoring system might be:

</p>

<ul><li>Match = 0</li>

<li>Indel = -1</li>

<li>Mismatch = -1</li></ul>

<p>For this system the alignment score will represent the edit distance between the two strings.

Different scoring systems can be devised for different situations, for example if gaps are considered very bad for your alignment you may use a scoring system that penalises gaps heavily, such as:

</p>

<ul><li>Match = 1</li>

<li>Indel = -10</li>

<li>Mismatch = -1</li></ul>

<p><br>

</p>

<div class="mw-heading mw-heading3"><h3 id="Similarity_matrix">Similarity matrix</h3></div>

<p>More complicated scoring systems attribute values not only for the type of alteration, but also for the letters that are involved. For example, a match between A and A may be given 1, but a match between T and T may be given 4. Here (assuming the first scoring system) more importance is given to the Ts matching than the As, i.e. the Ts matching is assumed to be more significant to the alignment. This weighting based on letters also applies to mismatches.

</p><p>In order to represent all the possible combinations of letters and their resulting scores a similarity matrix is used. The similarity matrix for the most basic system is represented as:

</p>

</th>

<th scope="col">A

</th>

<th scope="col">G

</th>

<th scope="col">C

</th>

<th scope="col">T

</th></tr>

<th scope="row">A

</th>

<td>−1

</td></tr>

<th scope="row">G

</th>

<td>−1

</td></tr>

<th scope="row">C

</th>

<td>−1

</td></tr>

<th scope="row">T

</th>

<td>1

</td></tr></tbody></table>

<p>Each score represents a switch from one of the letters the cell matches to the other. Hence this represents all possible matches and mismatches (for an alphabet of ACGT). Note all the matches go along the diagonal, also not all the table needs to be filled, only this triangle because the scores are reciprocal.= (Score for A → C = Score for C → A). If implementing the T-T = 4 rule from above the following similarity matrix is produced:

</p>

</th>

<th scope="col">A

</th>

<th scope="col">G

</th>

<th scope="col">C

</th>

<th scope="col">T

</th></tr>

<th scope="row">A

</th>

<td>−1

</td></tr>

<th scope="row">G

</th>

<td>−1

</td></tr>

<th scope="row">C

</th>

<td>−1

</td></tr>

<th scope="row">T

</th>

<td>4

</td></tr></tbody></table>

<p>Different scoring matrices have been statistically constructed which give weight to different actions appropriate to a particular scenario. Having weighted scoring matrices is particularly important in protein sequence alignment due to the varying frequency of the different amino acids. There are two broad families of scoring matrices, each with further alterations for specific scenarios:

</p>

<li><a href="BLOSUM" title="BLOSUM">BLOSUM</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Gap_penalty">Gap penalty</h3></div>

<p>When aligning sequences there are often gaps (i.e. indels), sometimes large ones. Biologically, a large gap is more likely to occur as one large deletion as opposed to multiple single deletions. Hence two small indels should have a worse score than one large one. The simple and common way to do this is via a large gap-start score for a new indel and a smaller gap-extension score for every letter which extends the indel. For example, new-indel may cost -5 and extend-indel may cost -1. In this way an alignment such as:

</p>

<pre>GAAAAAAT

G--A-A-T

</pre>

<p>which has multiple equal alignments, some with multiple small alignments will now align as:

</p>

<pre>GAAAAAAT

GAA----T

</pre>

<p>or any alignment with a 4 long gap in preference over multiple small gaps.

</p>

<div class="mw-heading mw-heading2"><h2 id="Advanced_presentation_of_algorithm">Advanced presentation of algorithm</h2></div>

<p>Scores for aligned characters are specified by a <a href="Similarity_matrix" class="mw-redirect" title="Similarity matrix">similarity matrix</a>. Here, <span class="texhtml"><i>S</i>(<i>a</i>, <i>b</i>)</span> is the similarity of characters <i>a</i> and <i>b</i>. It uses a linear <a href="Gap_penalty" title="Gap penalty">gap penalty</a>, here called <span class="texhtml mvar" style="font-style:italic;">d</span>.

</p><p>For example, if the similarity matrix was

</p>

</th>

<th scope="col">A

</th>

<th scope="col">G

</th>

<th scope="col">C

</th>

<th scope="col">T

</th></tr>

<th scope="row">A

</th>

<td>−4

</td></tr>

<th scope="row">G

</th>

<td>−3

</td></tr>

<th scope="row">C

</th>

<td>0

</td></tr>

<th scope="row">T

</th>

<td>8

</td></tr></tbody></table>

<p>then the alignment:

</p>

<pre>AGACTAGTTAC

CGA---GACGT

</pre>

<p>with a gap penalty of −5, would have the following score:

</p>

<p>To find the alignment with the highest score, a two-dimensional <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a> (or <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a>) <i>F</i> is allocated. The entry in row <i>i</i> and column <i>j</i> is denoted here by

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{ij}}</annotation>

</semantics>

</math></span><img src="./9f0a0c66fea9dad672268a8392d5c530e2d3f8e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.972ex; height:2.843ex;" alt="{\displaystyle F_{ij}}" loading="lazy"></span>. There is one row for each character in sequence <i>A</i>, and one column for each character in sequence <i>B</i>. Thus, if aligning sequences of sizes <i>n</i> and <i>m</i>, the amount of memory used is in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(nm)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(nm)}</annotation>

</semantics>

</math></span><img src="./051245e657739f572fe7902c817ea9103c687fb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.018ex; height:2.843ex;" alt="{\displaystyle O(nm)}" loading="lazy"></span>. <a href="Hirschberg's_algorithm" title="Hirschberg's algorithm">Hirschberg's algorithm</a> only holds a subset of the array in memory and uses <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (\min\{n,m\})}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (\min\{n,m\})}</annotation>

</semantics>

</math></span><img src="./a158767662e2f55a403ac654db74dd91942342ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.287ex; height:2.843ex;" alt="{\displaystyle \Theta (\min\{n,m\})}" loading="lazy"></span> space, but is otherwise similar to Needleman-Wunsch (and still requires <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(nm)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(nm)}</annotation>

</semantics>

</p><p>As the algorithm progresses, the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{ij}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{ij}}</annotation>

</semantics>

</math></span><img src="./9f0a0c66fea9dad672268a8392d5c530e2d3f8e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.972ex; height:2.843ex;" alt="{\displaystyle F_{ij}}" loading="lazy"></span> will be assigned to be the optimal score for the alignment of the first <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=0,\dotsc ,n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=0,\dotsc ,n}</annotation>

</semantics>

</math></span><img src="./1a57301a01dbbb2868686131483a2681b262a548.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.636ex; height:2.509ex;" alt="{\displaystyle i=0,\dotsc ,n}" loading="lazy"></span> characters in <i>A</i> and the first <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=0,\dotsc ,m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=0,\dotsc ,m}</annotation>

</semantics>

</math></span><img src="./564c3edf3098b95d4555b5486aefa1bc748b8abe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:12.464ex; height:2.509ex;" alt="{\displaystyle j=0,\dotsc ,m}" loading="lazy"></span> characters in <i>B</i>. The <a href="Bellman_equation#Bellman's_principle_of_optimality" title="Bellman equation">principle of optimality</a> is then applied as follows:

</p>

<ul><li>Basis:</li></ul>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{0j}=d*j}</annotation>

</semantics>

</math></span><img src="./4d4c08d197aba91b6d2fd553da2de6b8db428dbe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.693ex; height:2.843ex;" alt="{\displaystyle F_{0j}=d*j}" loading="lazy"></span></dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{i0}=d*i}</annotation>

</semantics>

</math></span><img src="./32566f595bc25bdcf53850703414cc2de106b3dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.428ex; height:2.509ex;" alt="{\displaystyle F_{i0}=d*i}" loading="lazy"></span></dd></dl>

<ul><li>Recursion, based on the principle of optimality:</li></ul>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),\;F_{i,j-1}+d,\;F_{i-1,j}+d)}</annotation>

</semantics>

</math></span><img src="./09ff4bd3d3ae737a9c71892887a1d30da4c9d78b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:54.765ex; height:3.009ex;" alt="{\displaystyle F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),\;F_{i,j-1}+d,\;F_{i-1,j}+d)}" loading="lazy"></span></dd></dl>

<p>The pseudo-code for the algorithm to compute the F matrix therefore looks like this:

</p>

<pre>d ← Gap penalty score

<b>for</b> i = 0 <b>to</b> <b>length</b>(A)

F(i,0) ← d * i

<b>for</b> j = 0 <b>to</b> <b>length</b>(B)

F(0,j) ← d * j

<b>for</b> i = 1 <b>to</b> <b>length</b>(A)

<b>for</b> j = 1 <b>to</b> <b>length</b>(B)

{

Match ← F(i−1, j−1) + S(A<sub>i</sub>, B<sub>j</sub>)

Delete ← F(i−1, j) + d

Insert ← F(i, j−1) + d

F(i,j) ← <b>max</b>(Match, Insert, Delete)

}

</pre>

<p>Once the <i>F</i> matrix is computed, the entry <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{nm}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{nm}}</annotation>

</semantics>

</math></span><img src="./739121f821cf200c4155fdf9047a9b158d19b085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.156ex; height:2.509ex;" alt="{\displaystyle F_{nm}}" loading="lazy"></span> gives the maximum score among all possible alignments. To compute an alignment that actually gives this score, you start from the bottom right cell, and compare the value with the three possible sources (Match, Insert, and Delete above) to see which it came from. If Match, then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{i}}</annotation>

</semantics>

</math></span><img src="./1aed3b5def921afbe6cc48aaf8f9b11c6f1c1e2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.543ex; height:2.509ex;" alt="{\displaystyle A_{i}}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B_{j}}</annotation>

</semantics>

</math></span><img src="./ea2c69d0fec8f10eb21aa996ca50219be25fc223.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.674ex; height:2.843ex;" alt="{\displaystyle B_{j}}" loading="lazy"></span> are aligned, if Delete, then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{i}}</annotation>

</semantics>

</math></span><img src="./1aed3b5def921afbe6cc48aaf8f9b11c6f1c1e2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.543ex; height:2.509ex;" alt="{\displaystyle A_{i}}" loading="lazy"></span> is aligned with a gap, and if Insert, then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B_{j}}</annotation>

</semantics>

</math></span><img src="./ea2c69d0fec8f10eb21aa996ca50219be25fc223.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.674ex; height:2.843ex;" alt="{\displaystyle B_{j}}" loading="lazy"></span> is aligned with a gap. (In general, more than one choice may have the same value, leading to alternative optimal alignments.)

</p>

<pre>AlignmentA ← ""

AlignmentB ← ""

i ← <b>length</b>(A)

j ← <b>length</b>(B)

<b>while</b> (i > 0 <b>or</b> j > 0)

{

<b>if</b> (i > 0 <b>and</b> j > 0 <b>and</b> F(i, j) == F(i−1, j−1) + S(A<sub>i</sub>, B<sub>j</sub>))

{

AlignmentA ← A<sub>i</sub> + AlignmentA

AlignmentB ← B<sub>j</sub> + AlignmentB

i ← i − 1

j ← j − 1

}

<b>else</b> <b>if</b> (i > 0 <b>and</b> F(i, j) == F(i−1, j) + d)

{

AlignmentA ← A<sub>i</sub> + AlignmentA

AlignmentB ← "−" + AlignmentB

i ← i − 1

}

{

AlignmentA ← "−" + AlignmentA

AlignmentB ← B<sub>j</sub> + AlignmentB

j ← j − 1

}

</pre>

<div class="mw-heading mw-heading2"><h2 id="Complexity">Complexity</h2></div>

<p>Computing the score <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{ij}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{ij}}</annotation>

</semantics>

</math></span><img src="./9f0a0c66fea9dad672268a8392d5c530e2d3f8e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.972ex; height:2.843ex;" alt="{\displaystyle F_{ij}}" loading="lazy"></span> for each cell in the table is an <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math></span><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"></span> operation. Thus the time complexity of the algorithm for two sequences of length <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math></span><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"></span> is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn)}</annotation>

</semantics>

</math></span><img src="./89ea09572a098b4762141a22c43a7ba1c20051cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.018ex; height:2.843ex;" alt="{\displaystyle O(mn)}" loading="lazy"></span>.<sup id="cite_ref-:0_3-0" class="reference"><a href="#cite_note-:0-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> It has been shown that it is possible to improve the running time to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn/\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn/\log n)}</annotation>

</semantics>

</math></span><img src="./cbffde729ef3c8c6081ebe2d1fbf4fe74b9347ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.321ex; height:2.843ex;" alt="{\displaystyle O(mn/\log n)}" loading="lazy"></span> using the <a href="Method_of_Four_Russians" title="Method of Four Russians">Method of Four Russians</a>.<sup id="cite_ref-:0_3-1" class="reference"><a href="#cite_note-:0-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Since the algorithm fills an <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\times m}</annotation>

</semantics>

</math></span><img src="./d82325a2a02ad79bc7c347ba9702ad46eb0de824.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.276ex; height:1.676ex;" alt="{\displaystyle n\times m}" loading="lazy"></span> table the space complexity is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn).}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn).}</annotation>

</semantics>

</math></span><img src="./de6cd0ec0f1e877a29c376a0beffd6b19d9f1378.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.665ex; height:2.843ex;" alt="{\displaystyle O(mn).}" loading="lazy"></span><sup id="cite_ref-:0_3-2" class="reference"><a href="#cite_note-:0-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Historical_notes_and_algorithm_development">Historical notes and algorithm development</h2></div>

<p>The original purpose of the algorithm described by Needleman and Wunsch was to find similarities in the amino acid sequences of two proteins.<sup id="cite_ref-Needleman_1-2" class="reference"><a href="#cite_note-Needleman-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>Needleman and Wunsch describe their algorithm explicitly for the case when the alignment is penalized solely by the matches and mismatches, and gaps have no penalty (<i>d</i>=0). The original publication from 1970 suggests the <a href="Recursion" title="Recursion">recursion</a>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{ij}=\max _{h<i,k<j}\{F_{h,j-1}+S(A_{i},B_{j}),F_{i-1,k}+S(A_{i},B_{j})\}}</annotation>

</semantics>

</math></span><img src="./f54134d6fbda7851c01eed5aa6e53fcc2a915e02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:51.908ex; height:4.343ex;" alt="{\displaystyle F_{ij}=\max _{h<i,k<j}\{F_{h,j-1}+S(A_{i},B_{j}),F_{i-1,k}+S(A_{i},B_{j})\}}" loading="lazy"></span>.

</p><p>The corresponding dynamic programming algorithm takes cubic time. The paper also points out that the recursion can accommodate arbitrary gap penalization formulas:

</p>

<p>A penalty factor, a number subtracted for every gap made, may be assessed as a barrier to allowing the gap. The penalty factor could be a function of the size and/or direction of the gap. [page 444]

</p>

</blockquote>

<p>A better dynamic programming algorithm with quadratic running time for the same problem (no gap penalty) was introduced later<sup id="cite_ref-Sankoff_5-0" class="reference"><a href="#cite_note-Sankoff-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> by <a href="David_Sankoff" title="David Sankoff">David Sankoff</a> in 1972.

Similar quadratic-time algorithms were discovered independently

by T. K. Vintsyuk<sup id="cite_ref-Vintsyuk_6-0" class="reference"><a href="#cite_note-Vintsyuk-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> in 1968 for speech processing

(<a href="Dynamic_time_warping" title="Dynamic time warping">"time warping"</a>), and by Robert A. Wagner and <a href="Michael_J._Fischer" title="Michael J. Fischer">Michael J. Fischer</a><sup id="cite_ref-WagnerFischer_7-0" class="reference"><a href="#cite_note-WagnerFischer-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> in 1974 for string matching.

</p><p>Needleman and Wunsch formulated their problem in terms of maximizing similarity. Another possibility is to minimize the <a href="Levenshtein_distance" title="Levenshtein distance">edit distance</a> between sequences, introduced by <a href="Vladimir_Levenshtein" title="Vladimir Levenshtein">Vladimir Levenshtein</a>. Peter H. Sellers showed<sup id="cite_ref-Sellers_8-0" class="reference"><a href="#cite_note-Sellers-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> in 1974 that the two problems are equivalent.

</p><p>The Needleman–Wunsch algorithm is still widely used for optimal <a href="Sequence_alignment#Global_and_local_alignments" title="Sequence alignment">global alignment</a>, particularly when the quality of the global alignment is of the utmost importance. However, the algorithm is expensive with respect to time and space, proportional to the product of the length of two sequences and hence is not suitable for long sequences.

</p><p>Recent development has focused on improving the time and space cost of the algorithm while maintaining quality. For example, in 2013, a Fast Optimal Global Sequence Alignment Algorithm (FOGSAA),<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> suggested alignment of nucleotide/protein sequences faster than other optimal global alignment methods, including the Needleman–Wunsch algorithm. The paper claims that when compared to the Needleman–Wunsch algorithm, FOGSAA achieves a time gain of 70–90% for highly similar nucleotide sequences (with > 80% similarity), and 54–70% for sequences having 30–80% similarity.

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications_outside_bioinformatics">Applications outside bioinformatics</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Computer_stereo_vision">Computer stereo vision</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Computer_stereo_vision" title="Computer stereo vision">Computer stereo vision</a></div>

<p>Stereo matching is an essential step in the process of 3D reconstruction from a pair of stereo images. When images have been rectified, an analogy can be drawn between aligning nucleotide and protein sequences and matching <a href="Pixels" class="mw-redirect" title="Pixels">pixels</a> belonging to <a href="Scan_lines" class="mw-redirect" title="Scan lines">scan lines</a>, since both tasks aim at establishing optimal correspondence between two strings of characters.

</p><p>Although in many applications image rectification can be performed, e.g. by <a href="Camera_resectioning" title="Camera resectioning">camera resectioning</a> or calibration, it is sometimes impossible or impractical since the computational cost of accurate rectification models prohibit their usage in <a href="Real-time_computing" title="Real-time computing">real-time</a> applications. Moreover, none of these models is suitable when a camera lens displays unexpected <a href="Distortions" class="mw-redirect" title="Distortions">distortions</a>, such as those generated by raindrops, weatherproof covers or dust. By extending the Needleman–Wunsch algorithm, a line in the 'left' image can be associated to a curve in the 'right' image by finding the alignment with the highest score in a three-dimensional array (or matrix). Experiments demonstrated that such extension allows dense pixel matching between unrectified or distorted images.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Wagner%E2%80%93Fischer_algorithm" title="Wagner–Fischer algorithm">Wagner–Fischer algorithm</a></li>

<li><a href="Smith%E2%80%93Waterman_algorithm" title="Smith–Waterman algorithm">Smith–Waterman algorithm</a></li>

<li><a href="Sequence_mining" class="mw-redirect" title="Sequence mining">Sequence mining</a></li>

<li><a href="Levenshtein_distance" title="Levenshtein distance">Levenshtein distance</a></li>

<li><a href="Dynamic_time_warping" title="Dynamic time warping">Dynamic time warping</a></li>

<li><a href="Sequence_alignment" title="Sequence alignment">Sequence alignment</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFNeedleman,_Saul_B.Wunsch,_Christian_D.1970" class="citation journal cs1">Needleman, Saul B. & Wunsch, Christian D. (1970). "A general method applicable to the search for similarities in the amino acid sequence of two proteins". <i>Journal of Molecular Biology</i>. <b>48</b> (3): <span class="nowrap">443–</span>53. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-2836%2870%2990057-4">10.1016/0022-2836(70)90057-4</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/5420325">5420325</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.britannica.com/EBchecked/topic/1334661/bioinformatics/285871/Goals-of-bioinformatics#ref1115380">"bioinformatics"</a><span class="reference-accessdate">. Retrieved <span class="nowrap">10 September</span> 2014</span>.</cite></span>

</li>

<li id="cite_note-:0-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_3-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:0_3-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFWing-Kin.2010" class="citation book cs1">Wing-Kin., Sung (2010). <i>Algorithms in bioinformatics : a practical introduction</i>. Boca Raton: Chapman & Hall/CRC Press. pp. <span class="nowrap">34–</span>35. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781420070330</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/429634761">429634761</a>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFMasekPaterson1980" class="citation journal cs1">Masek, William; Paterson, Michael (February 1980). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2880%2990002-1">"A faster algorithm computing string edit distances"</a>. <i>Journal of Computer and System Sciences</i>. <b>20</b>: <span class="nowrap">18–</span>31. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2880%2990002-1">10.1016/0022-0000(80)90002-1</a></span>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1721.1%2F148933">1721.1/148933</a></span>.</cite></span>

</li>

<li id="cite_note-Sankoff-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-Sankoff_5-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFSankoff_D1972" class="citation journal cs1">Sankoff D (1972). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC427531">"Matching sequences under deletion/insertion constraints"</a>. <i>Proceedings of the National Academy of Sciences of the USA</i>. <b>69</b> (1): <span class="nowrap">4–</span>6. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1972PNAS...69....4S">1972PNAS...69....4S</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1073%2Fpnas.69.1.4">10.1073/pnas.69.1.4</a></span>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC427531">427531</a></span>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/4500555">4500555</a>.</cite></span>

</li>

<li id="cite_note-Vintsyuk-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-Vintsyuk_6-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFVintsyuk_TK1968" class="citation journal cs1">Vintsyuk TK (1968). "Speech discrimination by dynamic programming". <i>Kibernetika</i>. <b>4</b>: <span class="nowrap">81–</span>88. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01074755">10.1007/BF01074755</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:123081024">123081024</a>.</cite></span>

</li>

<li id="cite_note-WagnerFischer-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-WagnerFischer_7-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFWagnerFischer1974" class="citation journal cs1">Wagner RA, Fischer MJ (1974). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321796.321811">"The string-to-string correction problem"</a>. <i><a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>. <b>21</b> (1): <span class="nowrap">168–</span>173. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321796.321811">10.1145/321796.321811</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13381535">13381535</a>.</cite></span>

</li>

<li id="cite_note-Sellers-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-Sellers_8-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFSellers_PH1974" class="citation journal cs1">Sellers PH (1974). "On the theory and computation of evolutionary distances". <i>SIAM Journal on Applied Mathematics</i>. <b>26</b> (4): <span class="nowrap">787–</span>793. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0126070">10.1137/0126070</a>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFChakrabortyBandyopadhyay2013" class="citation journal cs1">Chakraborty, Angana; Bandyopadhyay, Sanghamitra (29 April 2013). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3638164">"FOGSAA: Fast Optimal Global Sequence Alignment Algorithm"</a>. <i>Scientific Reports</i>. <b>3</b>: 1746. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2013NatSR...3.1746C">2013NatSR...3.1746C</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fsrep01746">10.1038/srep01746</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3638164">3638164</a></span>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/23624407">23624407</a>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFThevenon,_JMartinez-del-Rincon,_JDieny,_RNebel,_J-C2012" class="citation conference cs1">Thevenon, J; Martinez-del-Rincon, J; Dieny, R; Nebel, J-C (2012). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/257928290"><i>Dense pixel matching between unrectified and distorted images using dynamic programming</i></a>. International Conference on Computer Vision Theory and Applications. Rome.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://zhanglab.ccmb.med.umich.edu/NW-align">NW-align: A protein sequence-to-sequence alignment program by Needleman-Wunsch algorithm (online server and source code)</a></li>

<li><a rel="nofollow" class="external text" href="http://ds9a.nl/nwunsch">A live Javascript-based demo of Needleman–Wunsch</a></li></ul>

<p><br>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Strings176" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Strings176" style="font-size:114%;margin:0 4em"><a href="String_(computer_science)" title="String (computer science)">Strings</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="String_metric" title="String metric">String metric</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Approximate_string_matching" title="Approximate string matching">Approximate string matching</a></li>

<li><a href="Bitap_algorithm" title="Bitap algorithm">Bitap algorithm</a></li>

<li><a href="Damerau%E2%80%93Levenshtein_distance" title="Damerau–Levenshtein distance">Damerau–Levenshtein distance</a></li>

<li><a href="Edit_distance" title="Edit distance">Edit distance</a></li>

<li><a href="Gestalt_pattern_matching" title="Gestalt pattern matching">Gestalt pattern matching</a></li>

<li><a href="Hamming_distance" title="Hamming distance">Hamming distance</a></li>

<li><a href="Jaro%E2%80%93Winkler_distance" title="Jaro–Winkler distance">Jaro–Winkler distance</a></li>

<li><a href="Lee_distance" title="Lee distance">Lee distance</a></li>

<li><a href="Levenshtein_automaton" title="Levenshtein automaton">Levenshtein automaton</a></li>

<li><a href="Levenshtein_distance" title="Levenshtein distance">Levenshtein distance</a></li>

<li><a href="Wagner%E2%80%93Fischer_algorithm" title="Wagner–Fischer algorithm">Wagner–Fischer algorithm </a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="String-searching_algorithm" title="String-searching algorithm">String-searching algorithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Apostolico%E2%80%93Giancarlo_algorithm" title="Apostolico–Giancarlo algorithm">Apostolico–Giancarlo algorithm</a></li>

<li><a href="Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore string-search algorithm</a></li>

<li><a href="Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm" title="Boyer–Moore–Horspool algorithm">Boyer–Moore–Horspool algorithm</a></li>

<li><a href="Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" title="Knuth–Morris–Pratt algorithm">Knuth–Morris–Pratt algorithm</a></li>

<li><a href="Rabin%E2%80%93Karp_algorithm" title="Rabin–Karp algorithm">Rabin–Karp algorithm</a></li>

<li><a href="Raita_algorithm" title="Raita algorithm">Raita algorithm</a></li>

<li><a href="Trigram_search" title="Trigram search">Trigram search</a></li>

<li><a href="Two-way_string-matching_algorithm" title="Two-way string-matching algorithm">Two-way string-matching algorithm</a></li>

<li><a href="Zhu%E2%80%93Takaoka_string_matching_algorithm" title="Zhu–Takaoka string matching algorithm">Zhu–Takaoka string matching algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Multiple string searching</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Aho%E2%80%93Corasick_algorithm" title="Aho–Corasick algorithm">Aho–Corasick</a></li>

<li><a href="Commentz-Walter_algorithm" title="Commentz-Walter algorithm">Commentz-Walter algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Regular_expression" title="Regular expression">Regular expression</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Comparison_of_regular-expression_engines" class="mw-redirect" title="Comparison of regular-expression engines">Comparison of regular-expression engines</a></li>

<li><a href="Regular_grammar" title="Regular grammar">Regular grammar</a></li>

<li><a href="Thompson's_construction" title="Thompson's construction">Thompson's construction</a></li>

<li><a href="Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">Nondeterministic finite automaton</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Sequence_alignment" title="Sequence alignment">Sequence alignment</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="BLAST_(biotechnology)" title="BLAST (biotechnology)">BLAST</a></li>

<li><a href="Hirschberg's_algorithm" title="Hirschberg's algorithm">Hirschberg's algorithm</a></li>

<li><a href="Smith%E2%80%93Waterman_algorithm" title="Smith–Waterman algorithm">Smith–Waterman algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data_structure" title="Data structure">Data structure</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">DAFSA</a></li>

<li><a href="Substring_index" title="Substring index">Substring index</a>

<ul><li><a href="Suffix_array" title="Suffix array">Suffix array</a></li>

<li><a href="Suffix_automaton" title="Suffix automaton">Suffix automaton</a></li>

<li><a href="Suffix_tree" title="Suffix tree">Suffix tree</a></li>

<li><a href="Compressed_suffix_array" title="Compressed suffix array">Compressed suffix array</a></li>

<li><a href="LCP_array" title="LCP array">LCP array</a></li>

<li><a href="FM-index" title="FM-index">FM-index</a></li></ul></li>

<li><a href="Generalized_suffix_tree" title="Generalized suffix tree">Generalized suffix tree</a></li>

<li><a href="Ternary_search_tree" title="Ternary search tree">Ternary search tree</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parsing" title="Parsing">Parsing</a></li>

<li><a href="Pattern_matching" title="Pattern matching">Pattern matching</a></li>

<li><a href="Compressed_pattern_matching" title="Compressed pattern matching">Compressed pattern matching</a></li>

<li><a href="Longest_common_subsequence" title="Longest common subsequence">Longest common subsequence</a></li>

<li><a href="Longest_common_substring" title="Longest common substring">Longest common substring</a></li>

<li><a href="Sequential_pattern_mining" title="Sequential pattern mining">Sequential pattern mining</a></li>

<li>Sorting</li>

<li><a href="Semi-Thue_system" title="Semi-Thue system">String rewriting systems</a></li>

<li><a href="String_operations" title="String operations">String operations</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-12" href="https://en.wikipedia.org/wiki/?title=Needleman%E2%80%93Wunsch_algorithm&oldid=1300127474">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>